package model.algorithm;

import java.util.ArrayList;
import java.util.HashMap;

public class Bfs extends CommonSearcher {

	@Override
	public ArrayList<Action> search(SearchDomain sd) {
//		this.openList = new PriorityQueue<State>();				// I moved those two lines to the CommonSearcher Abs Class
//		this.closedList = new PriorityQueue<State>();
		
		this.openList.add(sd.getStartState());
		
		while (!openList.isEmpty()){
			State state = openList.poll();						// Pull the first node in the openList
			closedList.add(state);								// add it into the closedList
			
			if (state.equals(sd.getGoalState())){				// check if the pulled node is the goal node
				ArrayList<Action> actions = generatePath(state);	//generatePath - internal private method
				return actions;										// return the path the method have created
			}
			HashMap<Action, State> successors = sd.getAllPossibleMoves(state);			// getAllPossibleMoves is summons and the result will be kept in successors HMap
			for (Action act : successors.keySet()){					// will run through the successors HMap
				State nextState = successors.get(act);				// and check each it individually
				double newPathCost = state.getCost() + act.getCost();				// for the new cost (F)
				if (!openList.contains(nextState) && !closedList.contains(nextState)){
					nextState.setCost(newPathCost);
					nextState.setCameFrom(state);
					nextState.setPrevAct(act);
					openList.add(nextState);
				}
				else
				{
					if (newPathCost < nextState.getCost())
					{
						if(!openList.contains(nextState))
							openList.add(nextState);
						else{
							nextState.setCost(newPathCost);
							openList.add(nextState);
							
						}
					}
				}
			}
			
		} //Closing While loop
		return null;
	}

	// Back Tracing of the right path (through prevAct and cameFrom)
	private ArrayList<Action> generatePath(State state) {
		ArrayList<Action> actions = new ArrayList<Action>();
		do
		{
			actions.add(0, state.prevAct);
			state = state.cameFrom;
		} while (state.cameFrom != null);
		return actions;
	}
	
	@Override
	public String toString() {
		return "BFS";
	}

}
